package com.acwing.partition2;

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author `RKC`
 * @date 2021/12/12 16:55
 */
@SuppressWarnings("all")
public class AC154滑动窗口 {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] s = reader.readLine().split("\\s+");
        int n = Integer.parseInt(s[0]), k = Integer.parseInt(s[1]);
        int[] nums = new int[n];
        s = reader.readLine().split("\\s+");
        for (int i = 0; i < n; i++) nums[i] = Integer.parseInt(s[i]);
        List<Integer> answer = monotonicQueueMin(nums, k);
        for (int i = 0; i < answer.size(); i++) writer.write(answer.get(i) + " ");
        answer = monotonicQueueMax(nums, k);
        writer.write("\n");
        for (int i = 0; i < answer.size(); i++) writer.write(answer.get(i) + " ");
        writer.flush();
    }

    private static List<Integer> monotonicQueueMin(int[] nums, int k) {
        List<Integer> answer = new ArrayList<>();
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            if (!queue.isEmpty() && queue.peekFirst() < i - k + 1) queue.pollFirst();
            while (!queue.isEmpty() && nums[queue.peekLast()] > nums[i]) queue.pollLast();
            queue.addLast(i);
            if (i >= k - 1) answer.add(nums[queue.peekFirst()]);
        }
        return answer;
    }

    private static List<Integer> monotonicQueueMax(int[] nums, int k) {
        List<Integer> answer = new ArrayList<>();
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 0; i < nums.length; i++) {
            //合法区间[i-k+1, i]
            if(!queue.isEmpty() && queue.peekFirst() < i - k + 1) queue.pollFirst();
            //保证队列里面是一个单调递减的序列
            while (!queue.isEmpty() && nums[queue.peekLast()] < nums[i]) queue.pollLast();
            queue.addLast(i);
            if (i >= k - 1) answer.add(nums[queue.peekFirst()]);
        }
        return answer;
    }
}
